FIG. 1 (Prior Art) illustrates a contention-based CDMA ranging procedure. As illustrated in FIG. 1, in a CDMA ranging procedure, each Subscriber Stations (SS) randomly selects a CDMA ranging code from a predefined code pool, and transmits the ranging code to a Base Station (BS) via a randomly selected ranging slot from a limited number of ranging slots on a shared ranging channel provided by the BS. In the example of FIG. 1, SS1 transmits a CDMA Code sequence, indexed by CDMA Code1, on ranging slot 1, SS2 transmits a CDMA Code sequence, indexed by CDMA Code2, on ranging slot 3, and SS3 transmits a CDMA Code sequence, indexed by CDMA Code3, on ranging slot 11.
FIG. 2 (Prior Art) is a conventional message sequence diagram corresponding to the CDMA ranging procedure in FIG. 1. As illustrated in FIG. 2, after successful detection of the ranging codes, Base Station BS1 responses with ranging response (RNG_RSP) and uplink (UL) allocation information (CDMA Allocation IE). However, when many SSs attempt to initiate ranging procedures simultaneously, the SSs have to contend for access to the shared ranging channel. As a result, a ranging collision may occur in a wireless communications system employ conventional CDMA ranging.
FIG. 3 (Prior Art) illustrates an example of a CDMA ranging collision. Subscriber Stations SS1, SS2 and SS3 transmit different ranging codes on the same ranging slot simultaneously. The ranging codes collide and are thus not decodable by the Base Station BS1. As a result, BS1 will not transmit a successful ranging response back to the SSs. In the example of FIG. 3, after sending out an initial ranging code, each SS starts a predefined timer and waits for a ranging response from BS1 until the timer expires. After the timer expires, the SS will wait for a backoff window before retransmitting the ranging code for a next round of contention. Thus, the overall time delay caused by the ranging collision can be calculated based on the following formula:Tdelay=Ttimer+Tbackoff·Tframe—length where Tdelay is the total delay time, Ttimer is the timeout value, Tbackoff is the backoff time, and Tframe—length is the length of a frame.
FIG. 4 illustrates another example of a CDMA ranging failure. Subscriber station SS1 transmits an initial ranging code to the Base Station BS1. The ranging code is successfully received and decoded by BS1. Uplink (UL) resource, however, cannot be granted by BS1 due to insufficient bandwidth. Without receiving a successful UL grant, SS1 waits for timer expiration plus a backoff window, and then retransmits the ranging code for a next round of contention. The overall time delay can be calculated based on the following formula:Tdelay=Ttimer+Tbackoff·Tframe—length where Tdelay is the total delay time, Ttimer is the timeout value, Tbackoff is the backoff time, and Tframe—length is the length of a frame.
FIG. 5 illustrates a third example of a CDMA ranging procedure. In the example of FIG. 5, two Subscriber Stations SS1 and SS2 transmit the same ranging code on the same ranging slot. Base Station BS1 successfully decodes the ranging code and replies with a ranging response (RNG_RSP with ranging status=success) and a CDMA Allocation IE to both SS1 and SS2. When SS1 and SS2 receive the response from BS1, each SS sends a subsequent ranging request message simultaneously. As a result, the ranging request messages collide and the SSs no longer receive any response from BS1 until expiration of timer. The overall time delay can be calculated by the formula below:E[Tdelay]=1.5Ttimer+(Tbackoff+1)*Tframe—length where Tdelay is the total delay time, Ttimer is the timeout value, Tbackoff is the backoff time, and Tframe—length is the length of a frame.
FIG. 6 illustrates a diagram of the probability (Pcollision) of at least two users select the same code and the same slot. In the example of FIG. 6, the total number of users is thirty, the number of available ranging codes is sixty-four, and the number of available ranging slots is thirty. As the number of users increases, Pcollision also increases. When the number of user approaches thirty, Pcollision is very close to one. Pcollision can be expressed by the formula below:
            P      collision        =          1      -                                    ∏                          i              =              0                                      Nu              -              1                                ⁢                                          ⁢                      (                          NcNs              -              i                        )                                                (            NcNs            )                    Nu                                P      collision        =          1      -                                    ∏                          i              =              0                                      Nu              -              1                                ⁢                                          ⁢                      (                          NcNs              -              i                        )                                                (            NcNs            )                    Nu                    where Nu is the total number of users, Nc is the number of available ranging codes, and Ns is the number of available ranging slots.
If a large amount of collisions are caused by the contention access, then it becomes difficult for any of the SSs to complete its ranging procedure. Therefore, excessive time is needed for all the SSs to restart their ranging procedures, and much bandwidth on the shared ranging channel is wasted. The total latency introduced by ranging collision can be expressed by:
      T    total_delay    =            ∑              i        =        1            R        ⁢          T              delay        i            where Tdelay is the delay time for each SS, which depends on Ttimer, Tbackoff, and Tframe—length. In an IEEE 802.16e system, Ttimer ranges from 60 ms to 200 ms, Tbackoff ranges from 20 to 215 frames and Tframe—length is equal to 5 ms. Thus, it is possibly to take more than one second to complete the ranging procedure.
In a next generation 4G system, the maximum interruption time is 30 ms for intra-frequency handover and 100 ms for inter-frequency handover. Therefore, the latency introduced by ranging collision needs to be reduced in order to meet the requirements of 4G systems. Various efforts have been made to design a more efficient and faster ranging procedure.
LG Electronics proposed a differentiated random access scheme for contention-based bandwidth request ranging procedure. As shown in FIG. 7A, different timeout values are applied based on the priority of each bandwidth request (BR) indicator. To communicate the different priority and timeout values, a Base Station may broadcast a map of priority and timeout value to all the Subscriber Stations. For example, real-time service (rtPS) and extended real-time service (ertPS) are both high priority services having a shorter timeout value of 50 ms, while non real-time service (nrtPS) and best effort (BE) are low priority services having a longer timeout value of 100 ms.
FIG. 7B is a message sequence diagram of a differentiated bandwidth request ranging procedure proposed by LG Electronics. As illustrated in FIG. 7B, high priority services such as rtPS have a shorter timeout and thus a shorter delay while low priority services such as nrtPS have a longer timeout and thus a longer delay. During this ranging procedure, however, the SS still waits for timer expiration while contention resolution remains unhandled. Furthermore, such differentiated random access scheme is not applicable to random access channels of equal opportunity such as the ranging channel for initial ranging.